const common = require('./base/common');

/**
 * 778. 水位上升的泳池中游泳
 * 
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function(grid) {
    // 找到最大时间
    let maxT = -Infinity, N = grid.length;
    for(let i=0; i < N; ++i) {
        for(let j=0; j < N; ++j) {
            maxT = Math.max(grid[i][j], maxT);
        }
    }

    // 二分法求解
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let left = 0, right = maxT, ans = maxT;
    while(left < right) {
        let mid = (left + right) >> 1;
        let queue = [[0, 0]], 
            seen = new Array(N * N).fill(0);
        while(queue.length > 0) {
            let p = queue.shift();
            for(let dir of dirs) {
                let x = p[0] + dir[0], y = p[1] + dir[1];
                if(x >= 0 && 
                    x < N && 
                    y >= 0 && 
                    y < N && 
                    seen[x * N + y] == 0 &&
                    Math.max(grid[x][y], mid) == Math.max(grid[p[0]][p[1]], mid)) {
                    seen[x * N + y] = 1;
                    queue.push([x, y]);
                }
            }
        }

        if(seen[N * N - 1]) {
            ans = mid;
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return ans;
};

common.testing([
    [[0,2],[1,3]],
    [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
], [3, 16])(x => swimInWater(x));